/**
 *	EPAM_2048_Hero()
 * Description: A method returns tile moving direction.
 * @param  {int[][]} matrix
 *		current tile values on board, null if no
 *	@return {type}
 *		return one of 'U'(up),'D'(down),'L'(left),'R'(right)
 */

function ifDoMove(arr, direction, debug = false) {
    const noZeroArr = arr.filter((item) => item > 0);
    // Do reverse, so that we can use same merge logic with other case. 
    // Be ware that result should reverse back as well
    if (direction == 'D' || direction == 'R') {
        noZeroArr.reverse();
    }

    const noZeroArrNew = [];
    let score = 0;
    let merged = false; // *生成的item不参与后面的计算
    let mergedCount = 0; // 合并次数在非常重要，可以游戏时间更长；特别在棋盘上的空格少的时候
    let movable = false;

    // so just try compare from 1st the last....
    noZeroArr.reduce((prev, curr, index) => {
        const len = prev.length;
        if (len > 0 && prev[len - 1] === curr && !merged) {
            noZeroArrNew[len - 1] = curr * 2;
            score += curr * 2;
            merged = true;
            movable = true;
            mergedCount++
            if (debug) console.log('++  ', noZeroArrNew, curr);
            // console.log(arr, direction, noZeroArrNew, score, mergedCount);
        } else {
            noZeroArrNew.push(curr);
            merged = false;
        }
        return noZeroArrNew;
    }, []);

    // fill with 0
    const numToFill = 4 - noZeroArrNew.length;
    for (let i = 0; i < numToFill; i++) {
        noZeroArrNew.push(0);
    }

    // do reverse in case
    if (direction == 'D' || direction == 'R') {
        noZeroArrNew.reverse();
    }

    // if (direction == 'U') {
    //     console.log('>>>>> ', noZeroArrNew, arr);
    // }
    if (!movable) {
        for (let i = 0; i < 4; i++) {
            // if (direction == 'U') {
            //     console.log('>>>>> ', noZeroArrNew[i], arr[i]);
            // }
            if (noZeroArrNew[i] != arr[i]) {
                movable = true;
                break;
            }
        }
    }
    if (debug && mergedCount > 0) {
        console.log(arr, direction, movable, noZeroArrNew, score, mergedCount);
    }
    return {
        arrNew: noZeroArrNew,
        direction,
        score,
        movable,
        mergedCount,
    };
}

/**
 * generate item with 90% 2, and 10% 4
 */
function generateItem() {
    const r = Math.random();
    return r > 0.9 ? 4 : 2;
}

function addItemToMatrix(matrix) {
    // console.log('addItemToMatrix', matrix);
    let numberOfZero = 0;
    // matrix.map((row) => {
    //     numberOfZero += row.filter((item) => item == 0).length;
    //     return null;
    // });
    for (let i = 0; i < matrix.length; i++) {
        numberOfZero += matrix[i].filter((item) => item == 0).length;
    }

    // 空白越多，中标概率越低。
    // 限制一下
    if (numberOfZero > MIN_ZERO_COUNT) {
        return matrix
    };

    const targetIndex = Math.floor(Math.random() * numberOfZero);

    let count = 0;
    const newArr = [[], [], [], []];
    const newItem = generateItem();
    // console.log('numberOfZero: ', numberOfZero, 'targetIndex: ', targetIndex, 'newItem: ', newItem );
    for (let i = 0; i < 4; i++) {
        for (let j = 0; j < 4; j++) {
            if (matrix[i][j] == 0) {
                newArr[i][j] = count == targetIndex ? newItem : matrix[i][j];
                count++
            } else {
                newArr[i][j] = matrix[i][j];
            }
        }
    }
    // console.log(newArr);
    return newArr;
}

/**
 * 
 * @param {*} matrix : 棋盘
 * @param {*} direction : 移动方向： U, D, L, R
 * 
 * @return {newArr, score, moved} ： 移动后的新arr 和 分数
 * 有可能没有发生移动，分数是0
 * 发生移动了，但是分数也是0
 */
function doMove(matrix, direction, weight) {
    // separate matrix to arr
    const myArrList = [];
    if (direction == 'R' || direction == 'L') {
        // row
        for (let i = 0; i < 4; i++) {
            myArrList.push([...matrix[i]]);
        }
    } else {
        // column
        for (let i = 0; i < 4; i++) {
            const row = [];
            for (let j = 0; j < 4; j++) {
                row.push(matrix[j][i]);
            }
            myArrList.push([...row]);
        }
    }
    // console.log('** ',direction, myArrList);

    // do move for every row
    // in case of depth = 1
    const scoreArr = [];
    const matrixNew = [];
    let movable = false;
    let totalScore = 0;
    let totalMergedCount = 0;
    const movableDetail = [];
    for (let i = 0; i < 4; i++) {
        // {
        //     arrNew,
        //     direction,
        //     score,
        //     movable,
        // }
        const result = ifDoMove(myArrList[i], direction);
        // console.log('^^^', direction, myArrList[i], result.movable);
        // console.log('row -> ', i, result);
        scoreArr.push(result);
        if (direction == 'R' || direction == 'L') {
            matrixNew.push([...result.arrNew]);
        }
        movableDetail.push({
            direction,
            idx: i,
            movable: result.movable,
        });
        movable = movable || result.movable;
        totalScore += result.score;
        totalMergedCount += result.mergedCount;
    }

    if (direction == 'U' || direction == 'D') {
        for (let i = 0; i < 4; i++) {
            const row = [];
            for (let j = 0; j < 4; j++) {
                const { arrNew } = scoreArr[j]
                row.push(arrNew[i]);
            }
            // console.log(row);
            matrixNew.push([...row]);
        }
    }

    //  console.log(direction, weight[direction], totalScore, totalScore * (1 + weight[direction]));
    // 当单体过大时，weight严重影响了最优的方向
    const weightScore = weight * RATIO_WEIGHT;
    // console.log(weight, direction, weightScore);
    // movable means totalMergedCount > 0
    // 如果可以移动的次数越多，加成约多，放大倍率取决于RATIO_MERGED_COUNT
    const mergedCountScore = movable ? (totalMergedCount - 1) * RATIO_MERGED_COUNT : 0;
    // console.log('* doMove * ', matrix, direction, movable, matrixNew);
    // console.log('* info -->> ', totalScore, weightScore, totalMergedCount, mergedCountScore);
    // if (totalMergedCount > 0){
    //     console.log('----<<>> ', totalMergedCount);
    // }
    console.log(totalScore + weightScore + mergedCountScore, totalScore, weightScore, mergedCountScore, totalMergedCount);
    return {
        direction,
        movable,
        score: totalScore + weightScore + mergedCountScore,
        matrixNew,
        mergedCount: totalMergedCount,
        totalScore,
        weightScore,
        mergedCountScore,
        movableDetail,
    };
}

// let matrix = [
// [0, 2, 4, 8],
// [0, 2, 4, 8],
// [8, 4, 2, 0],
// [8, 4, 2, 0],
// ];
// doMove(matrix, 'R');
// doMove(matrix, 'D');


// 棋盘分成4大块，计算每块当前的权重。看棋盘上最大的数字在哪个区域
/**
 *  {L, U}        {R, U}
 * [2,     0,  ｜  0,    0],
 * [4,     0,  ｜  0,    4],
 * ------------｜-----------
 * [4,     0,  ｜  0,    0],
 * [8,     16, ｜  8,    0]
 *  {L, D}        {R, D}
 * 
 * [0,0, | 0,0,],
 * [0,0, | 0,2,],
 * ---------------
 * [0,0, | 0,8,],
 * [0,2, | 4,16]
 */
function calculateWeight(board) {
    // console.log('calculateWeight', board);
    let total = 0;
    let LU = 0;
    let RU = 0;
    let LD = 0;
    let RD = 0;

    for (let i = 0; i < 4; i++) {
        for (let j = 0; j < 4; j++) {
            const v = board[i][j] > 0 ? Math.log(board[i][j]) / Math.log(2) : 0;
            // console.log(board[i][j], v);
            total += v;
            if (j > 1) {
                if (i > 1) {
                    RD += v;
                } else {
                    RU += v;
                }
            } else {
                if (i > 1) {
                    LD += v;
                } else {
                    LU += v;
                }
            }
        }
    }

    // let tValue = 0;
    // for (let i = 0; i < 4; i++) {
    //     const tmpArr = board[i].filter((item) => item > 0);
    //     for (let j = 0; j < tmpArr.length; j++) {
    //         tValue += Math.log(tmpArr[j]) / Math.log(2);
    //     }
    // }
    // console.log({
    //     L: (LU + LD)/2,
    //     R: (RU + RD)/2,
    //     D: (LD + RD)/2,
    //     U: (LU + RU)/2,
    // });
    return {
        total,
        // L: (LU + LD) / 2 / total,
        // R: (RU + RD) / 2 / total,
        // D: (LD + RD) / 2 / total,
        // U: (LU + RU) / 2 / total,
        L: (LU + LD) ,
        R: (RU + RD) ,
        D: (LD + RD) ,
        U: (LU + RU) ,
    }
}

/**
 * 简单的上下左右移动的最优
 * 
 * [0   0   0   0]
 * [0   0   0   2]
 * [0   2   0   0]
 * [0   0   0   0]
 */

/**
 * 简单移动没有最优解
 * 1. 当前移动没有解，考虑当前移动情况下的下一步的收益 ****
 *      最大深度
 *      最大值元素优先位置
 *      最大值元素周边元素优先排
 * 2. 没有收益，只为移动棋盘
 */

function ruleOneScore (arr) {
    const noZeroArr = arr.filter((item) => item > 0);
    let value = 0;
    // 确保i+1不越界
    for (let i = 0; i < noZeroArr.length - 1; i++) {
        const current = Math.log(noZeroArr[i]) / Math.log(2);
        const next = Math.log(noZeroArr[i+1]) / Math.log(2);
        // 差值越小，说明相邻的2个数据越接近
        const tmp = current - next;
        value += tmp;
    }
    // value越小越好
    // console.log('ruleOneScore - ', value, arr, noZeroArr);
    return Math.abs(value);
}

/**
 * 
 * @param {*} matrix 
 * @returns x轴评分+y轴评分为当前移动后的 RuleOne的评分
 */
function calcRuleOne(matrix) {
    let xValue = 0;
    let yValue = 0;
    // console.log(' --- ROW --- ');
    for (let i = 0; i < 4; i++) {
        // row
        xValue += ruleOneScore(matrix[i]);
    }

    // console.log(' --- COLUMN --- ');
    for (let j = 0; j < 4; j++) {
        // column
        yValue += ruleOneScore([
            matrix[0][j],
            matrix[1][j],
            matrix[2][j],
            matrix[3][j],
        ]);
    }

    let tValue = 0;
    for (let i = 0; i < 4; i++) {
        const tmpArr = matrix[i].filter((item) => item > 0);
        for (let j = 0; j < tmpArr.length; j++) {
            tValue += Math.log(tmpArr[j]) / Math.log(2);
        }
    }

    const xyValue = xValue + yValue;
    // console.log(' --- ROW + COLUMN --- ',tValue, xyValue);
    return xyValue > 0 ? tValue / xyValue : tValue * 2;
}

function updateScoreWithRuleOne(item) {
    const { direction, movable, score, matrixNew } = item;
    if (!movable) return;
    const ruleOneScore = calcRuleOne(matrixNew);
    item.score += ruleOneScore;
    item.ruleOneScore = ruleOneScore;
}

function withRuleOneWeight(results) {
    // update results
    results.forEach((item) => {
        // console.log(` ****  ${item.direction}  ***** `);
        updateScoreWithRuleOne(item);
    });
}

function scoreNear(item, itemIdx, matrix, idx, direction) {
    // console.log('scoreNear', item, itemIdx, matrix, 'idx: ', idx, arr1, arr2);
    let score = 0;
    let xx = 0;

    // compare with Up one
    if (idx - 1 > -1) {
        const value1 = DIRECTIONS.indexOf(direction) > 2 ? matrix[idx - 1][itemIdx] : matrix[itemIdx][idx - 1];
        if (item == value1) xx = 2;
        if (item * 2 == value1 || item / 2 == value1) xx = 1;
        // console.log('U', xx, item, value1);
        score += item * xx;
    }
    
    // compare with Down one
    if (idx + 1 < 4) {
        xx = 0; // reset
        const value2 = DIRECTIONS.indexOf(direction) > 2 ? matrix[idx + 1][itemIdx] : matrix[itemIdx][idx + 1];
        if (item == value2) xx = 2;
        if (item * 2 == value2 || item / 2 == value2) xx = 1;
        // console.log('D', xx, item, value2);
        score += item * xx;
    }

    return score;
}

function doNear(arr) {
    // console.log('doNear', arr);
    const { matrixNew, movableDetail, score, direction } = arr;
    const movableInfo = movableDetail.filter((item) => item.movable);
    // console.log('doNear ++ ', movableInfo);
    if (!(movableInfo.length > 0)) {
        return;
    }
    let nearScore = 0;

    movableInfo.forEach(movableItem => {
        // console.log('doNear ++ ', movableItem, DIRECTIONS.indexOf(direction));
        let theArr = DIRECTIONS.indexOf(direction) > 1
            ? matrixNew[movableItem.idx]
            : [
                matrixNew[0][movableItem.idx],
                matrixNew[1][movableItem.idx],
                matrixNew[2][movableItem.idx],
                matrixNew[3][movableItem.idx],
            ];
        // console.log('theArr - ', theArr);
        theArr.forEach((item, itemIdx) => {
            nearScore += scoreNear(item, itemIdx, matrixNew, movableItem.idx, direction);
        });
    });
    // 
    arr.nearScore = nearScore;
    arr.score += nearScore * RATIO_NEAR_BY;
    // console.log('doNear -->> ', nearScore);
}

/**
 * 
 * @param {*} results 
 * 
 */
function calculateWithNearBy(results) {
    // const newResults = [...results].filter((item) => item.movable);
    // if (!(newResults.length > 0)) {
    //     return results;
    // }
    const newResults = [...results];

    // 取出方向
    const one = getBestOne(results);
    const idx = DIRECTIONS.indexOf(one.direction)
    const x = idx > 1 ? 'row' : 'column';
    console.log('--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ');
    console.log('--- calculateWithNearBy ---    >>>>', one.direction, x);
    console.log('--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ');
    
    const doNearArr = idx > 1 ? ['L', 'R'] : ['U', 'D'];
    // for (let i = 0; i < 2; i++) {
    //     doNearArr[i]
    // }
    doNearArr.map((item) => {
        doNear(newResults[DIRECTIONS.indexOf(item)]);
    });
    return newResults;
}

function getDepth(matrix) {
    let spaceNum = 0;
    matrix.forEach(row => {
        row.forEach(item => {
            if (item == 0) {
                spaceNum++;
            }
        })
    });
    // console.log(spaceNum);
    return DEPTH_MAX > spaceNum ? spaceNum : DEPTH_MAX;
}


function getBestOne(results) {
    // 去除不能移动的方向
    const allFineResults = results.filter((item) => item.movable);
    // sort by score desc
    allFineResults.sort((a, b) => b.score - a.score)
    // console.log('sorted by score: ', newArr);

    // best one
    return allFineResults[0];
}

// 递归深度越高，它的影响越小（因为递归深度越高，准确率越低）
function getRatio(max_depth, new_depth) {
    const current = max_depth - new_depth;
    return 0.5 / (current * current);
}

/**
 * 
 * @param {*} matrix 
 * @param {*} depth will be updated in roll
 * @param {*} info 
 * @param {*} max_depth will not change this value. just used as a const param
 * @returns 
 */
function rollInDepth(matrix, depth, info, max_depth) {
    // console.log('--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ');
    // console.log('--- rollInDepth Start ---    >>>>', depth, info);
    // console.log('--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ');
    
    const weight = calculateWeight(matrix);
    // console.log('wight ', weight, depth);

    // move
    // console.log(doMove(matrix, 'R'));
    const allResults = DIRECTIONS.map((item, index) => {
        let moreInfo = info + ' -> ' + item;
        const res = doMove(matrix, item, weight[item]);
        const { movable, matrixNew, score, mergedCount } = res;

        // console.log('-->> rollInDepth ', moreInfo);
        // console.log('depth - ', depth);
        // console.log('movable - ', movable);
        // console.log('score - ', score);
        // console.log('matrixNew - ', matrixNew);
        const new_depth = depth - 1;
        if (movable && new_depth > 0) {
            const xxx = rollInDepth(addItemToMatrix(matrixNew), new_depth, moreInfo, max_depth);
            // console.log('^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^');
            // console.log(xxx);
            // console.log('^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^');
            const { depthScore = 0 } = res;
            const dVal = xxx.score * getRatio(max_depth, new_depth);
            res.score += dVal;
            res.depthScore = depthScore + dVal;
            console.log('^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ', xxx.score, 'Ratio - ', dVal);
            return res;
        } else {
            return res;
        }
    });

    // 分析移动分（totalScore）最高的2个，哪个更优（不考虑权重）
    if (depth == max_depth) {
        // calculateWithNearBy(allResults);
        withRuleOneWeight(allResults);
    }

    const theBestOne = getBestOne(allResults);
    const { direction, movable, score, matrixNew, mergedCount } = theBestOne;

    if (depth == max_depth) {
        // console.log('*** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** ');
        // console.log('*** rollInDepth done ***    >>>>', depth, info);
        console.log('*** rollInDepth done ***', allResults, direction, matrixNew);
        // console.log('*** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** ');
    }
    return theBestOne;
}

const DIRECTIONS = ["U", "D", "L", "R"];
// 递归深度
const DEPTH_MAX = 3;
// 移动方向重量比率 （权重）
const RATIO_WEIGHT = 1.2;
// 移动方向相邻元素优越性比率
const RATIO_NEAR_BY = 0.8;
// 合并次数倍率
const RATIO_MERGED_COUNT = 1;
// 面板上空格的数量，是否填充item以提高递归准确率 ？？
const MIN_ZERO_COUNT = 2;


function EPAM_2048_Hero(board) {
    // fill zero
    for (let i = 0; i < 4; i++) {
        for (let j = 0; j < 4; j++) {
            board[j][i] += 0;
        }
    }

    // control depth
    const depth = getDepth(board);
    const bestOperation = rollInDepth(board, depth, 'root', depth);
    const {direction, movable, score, matrixNew, mergedCount} = bestOperation;
    console.log(board, direction, movable, matrixNew, score, mergedCount);
    return movable ? direction : null;

    // TEAM: Triple A
    // SECRET: AAA666
}
